package com.leetcode.recursive;

import org.junit.Test;

/**
 * @author: ZhouBert
 * @date: 2019/10/15
 * @description:	36. 有效的数独【这个题目比起八皇后简单很多了！】
 * B
 * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 *
 * 说明:
 *
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * 给定数独序列只包含数字 1-9 和字符 '.' 。
 * 给定数独永远是 9x9 形式的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-sudoku
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class IsValidSudoku36 {

	/**
	 * 只要证明数独是否有效即可，而不需要证明可解。所以只需要验证每个数字的合法性，以及通过递归驱动元素从[0,0]到[8,8]
	 * @param board
	 * @return
	 */
	public boolean isValidSudoku(char[][] board) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (!judge(board,i,j)){
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 判断一个点的数字是否合法
	 * @param board	数独棋盘
	 * @param i	行索引
	 * @param j	列索引
	 * @return	合法返回 true
	 */
	public boolean judge(char[][] board, int i, int j){
		///0.如果是.返回true
		if (board[i][j]=='.'){
			return true;
		}
		///1.判断一行
		for (int k = 0; k < 9; k++) {
			if (k==j){
				continue;
			}
			if (board[i][j]==board[i][k]){
				return false;
			}
		}

		///2.判断一列
		for (int k = 0; k < 9; k++) {
			if (k==i){
				continue;
			}
			if (board[i][j]==board[k][j]){
				return false;
			}
		}
		///3.判断3*3
		///todo:关键怎么去寻找对应关系--可以通过整除3进行计算。
		int beginI=i/3*3;
		int beginJ=j/3*3;
		int limitI=beginI+3;
		int limitJ=beginJ+3;
		for (int k = beginI; k < limitI; k++) {
			for (int l = beginJ; l < limitJ; l++) {
				if (i==k&&j==l){
					continue;
				}
				if (board[i][j]==board[k][l]){
					return false;
				}
			}
		}
		return true;

	}

	public static void main(String[] args) {
		char[][] input=new char[][]{
				{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}
		};
		IsValidSudoku36 isValidSudoku36 = new IsValidSudoku36();
		System.out.println(isValidSudoku36.isValidSudoku(input));
	}

	@Test
	public void test(){
		char[][] input=new char[][]{{'.','.','.','.','5','.','.','1','.'},{'.','4','.','3','.','.','.','.','.'},{'.','.','.','.','.','3','.','.','1'},{'8','.','.','.','.','.','.','2','.'},{'.','.','2','.','7','.','.','.','.'},{'.','1','5','.','.','.','.','.','.'},{'.','.','.','.','.','2','.','.','.'},{'.','2','.','9','.','.','.','.','.'},{'.','.','4','.','.','.','.','.','.'}};
		IsValidSudoku36 isValidSudoku36 = new IsValidSudoku36();
		System.out.println(isValidSudoku36.isValidSudoku(input));
	}
}
